package concurrensy.sorter;

import java.util.ArrayList;
import java.util.List;

public class OneThreadMergeSorter<T  extends Comparable<T>> implements MergeSorter<T>{

	@Override
	public List<T> mergeSort(List<T> listToSort) {
		List<T> result = new ArrayList<>();
		List<T> leftList = new ArrayList<>();
		List<T> rightList = new ArrayList<>();
		int center = findListCenter(listToSort);
		for(int count = 0; count <= center; count++){
			leftList.add(listToSort.get(count));
		}
		for(int count = center + 1; count < listToSort.size(); count++){
			rightList.add(listToSort.get(count));
		}	
		sort(leftList);
		sort(rightList);
		merge(result, leftList, rightList);
		return result;
	}

	private void merge(List<T> result, List<T> leftList, List<T> rightList) {
		while((!leftList.isEmpty()) && (!rightList.isEmpty())){
			if(leftList.get(0).compareTo(rightList.get(0)) < 0){
				result.add(leftList.get(0));
				leftList.remove(0);
			} else if(leftList.get(0).compareTo(rightList.get(0)) == 0) {
				result.add(leftList.get(0));
				result.add(rightList.get(0));
				leftList.remove(0);
				rightList.remove(0);
			} else {
				result.add(rightList.get(0));
				rightList.remove(0);
			}		
		}
		while((!leftList.isEmpty())){
			result.addAll(leftList);
			leftList.clear();
		}
		while((!rightList.isEmpty())){
			result.addAll(rightList);
			rightList.clear();
		}
	}

	private void sort(List<T> list) {
		for(int count = list.size() - 1; count > 0; count--){
			for(int i = 0 ; i < count ; i++){
				if(list.get(i).compareTo(list.get(i + 1)) > 0){
					swap(list, i, i + 1);
				}
			}
		}
	}
	
	private void swap(List<T> list, int el1, int el2){
		T temp1 = list.get(el1);
		T temp2 = list.get(el2);
		list.remove(el1);
		list.add(el1, temp2);
		list.remove(el2);
		list.add(el2, temp1);
	}

	private int findListCenter(List<T> listToSort) {
		int center;
		if((listToSort.size() % 2) == 0){
			center = (listToSort.size()/2) - 1;
		} else {
			center = listToSort.size()/2;
		}
		return center;
	}

}
